\section{Heur\'istica GRASP}

% \subsection{Presentaci\'on del problema}
\subsection{Resoluci\'on}
La idea de la busqueda local es buena para poder lograr una solucion 
util a un problema que de otra manera tendria un costo superior
al que se puede pagar o se esta dispuesto a pagar, en tiempo o complegidad. El problema
 es que la busqueda local tiende a quedarse con minimos o maximos 
locales. Dada una misma instancia la naturaleza deterministica de la busqueda
local hara que siempre se llegue al mismo resultado, y en caso de ser 
un minimo o maximo local, esto sera poco satisfactorio como aproximacion.
Para poder superar este obstaculo se plantea Grasp. \\
Grasp utiliza la misma tecnica que la busqueda local pero introduce la aleatoriedad 
para poder partir de un conjunto de soluciones factibles y tratar de mejorarlas mediante 
busqueda local. \\
El problema de encontrar un camino acotado optimo entre 2 nodos de un grafo
se aproxima en un primer momento con un algoritmo goloso aleatorizado. Este 
algoritmo es una variante de dijkstra que al momento de optar por 
mejorar una camino utiliza un valor random. La logica con la que se va
avanzando por lo nodos y mejorando caminos en base a los ejes del nodo actual, fue
modificada para que en algunos  casos se tome en cuenta un valor random como
indicador de que se debe modificar una ruta. El funcionamiento 
normal es que si la ruta conocida tiene mayor W2 (que es el valor que quiero optimizar)
que la ruta que puedo construir con las aristas que estoy conociendo en este paso. Entonces
mejoro esa ruta con esta nueva arista. Siempre iguando obviamente, el W1 siga cumpliendo mi cota.
A ese funcionamiento se agrego un random. Para que en determinados pasos
se opte por otro camino distinto del que posee menor W2. Asi mismo 
al momento de tomar el siguiente nodo al que avanzar, disjktra utiliza 
un heap. En este caso se utilizo un random. Esto termina haciendo que en algunos
casos se opte por desiciones golosas y en otros por desiciones aleatoreas.
Luego de generar caminos se utiliza busqueda local para poder lograr una mejora
de estas soluciones. Cada una de estas ejecuciones tendra un valor de W2 
que es el que tratamos de optimizar.\\
Luego de tener el ciclo que me genera resultados, resta ver como identificar 
cuando es suficiente, cuando tenemos ya el mejor resultado que vamos a poder tener. \\
Para esto se definieron varios contadores para poder controlar la terminacion del algoritmo. \\
Se definio un contador para identificar la cantidad de veces que saque la mejor solucion que conozco.
Otro para ver la cantidad de veces que no se encontro solucion. Esto es para que en el caso de que el 
greedy aleatorizado no encuentre una solucion para comenzar una cantidad fija de veces se termine. 
Tambien, en caso de haber mas de K soluciones que no mejoran la mejor encontrada. Todas salen peores a la que tengo. 
Estas constantes fueron fijadas en base a observaciones en los valores. 
Se fijo en 10 cada una de estas constantes(cantidad de veces que se obtiene un resultado 
y no se mejora, cantidad de veces que no se obtiene resultado para comenzar la busqueda local)




\subsection{Pseudoc\'odigo}

En este algoritmo al basarse en los algoritmos anteriores se resumio su pseudocodigo
para que sea mas claro ver en que difiere, o que es lo que agrega a 
las tecnicas anteriores. 
\begin{verbatim}
Grasp (Grafo G){
    termino  = 0
    mejorW2 = Null
    mejorR = Null
    while  not termino {
        R  = CalcularCaminoDijkstraRandom(G)
        if (R){
            R=busquedaLocal(R)
            if (R->w2 < mejorW2){
                mejorW2 = R->w2
                mejorR = R
                noMejora = 0
            }else{
                noMejora =  noMejora + 1
            }
            if (noMejora > 10 ) termino = 1

        }else{
            sinSolucion = sinSolucion + 1 
            if (sinSolucion > 10 ) termino = 1
        }
    }
    return mejorR
}
\end{verbatim}

\subsection{An\'alisis de complejidad}

\subsection{Experimentacion}
a experimentacion se realizo en base a grafos armados de manera random, los mismos se crearon mediante un script en python que se encuentra dentro de la carpeta src. se generaron 500 instancias con nodos que se elegian de manera random entre 5 y 200, en base a la cantidad de nodos se genero el grafo completo y se tomo 3/4 de las aristas para que no sea el grafo completo ya que si todos los nodos eran adyacentes entre si y no servia tener todos los casos asi. Los valores w1 y w2 de las aristas son numeros random entre 1 y 100 , el valor de k se genera al final luego de sumar todas las aristas.

\includegraphics[scale=0.8]{grasp.jpeg} \\
Como se puede observar el algoritmo tiene un orden de complejidad polinomial de \Ode{n^2}, se puede ver que en muchos casos de tamaño de entrada grande el tiempo de ejecucion es chico esto puede ser porque no encontro camino o porque el camino era trivial de encontrar.
Para tomar la complejidad se tuvo en cuenta el algoritmo que genera la solucion factible y luego la que realiza la busqueda local, ambas tienen misma complejidad y no afecta la busqueda local a el total del algoritmo.
\subsection{C\'odigo de fuente}
\begin{verbatim}
   codigo.
\end{verbatim}
